package com.leetcode.partition8;

/**
 * @author `RKC`
 * @date 2021/9/6 18:12
 */
public class LC738单调递增的数字 {

    public static int monotoneIncreasingDigits(int n) {
        return greedy(n);
    }

    public static void main(String[] args) {
        System.out.println(monotoneIncreasingDigits(1234));
    }

    private static int greedy(int n) {
        char[] numberArray = String.valueOf(n).toCharArray();
        // 从后往前遍历（避免结果被覆盖），局部最优：numberArray[i]<=numberArray[i-1]，numberArray[i-1]--再numberArray[i]='9'，
        // 可以保证这两位变为最大单调递增整数。全局最优：得到小于等于N的最大单调递增的数字
        int index = numberArray.length;          //记录从哪个索引的位置开始，以后的所有内容都是9
        for (int i = numberArray.length - 1; i > 0; i--) {
            if (numberArray[i] < numberArray[i - 1]) {          //不是单调递增的数字序列
//                numberArray[i] = '9';
                index = i;
                numberArray[i - 1]--;
            }
        }
        for (int i = index; i < numberArray.length; i++) {
            numberArray[i] = '9';
        }
        return Integer.parseInt(new String(numberArray));
    }
}
